The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Given an off-line sequence S of n set-manipulation operations, we investigate the parallel complexity of evaluating S (i.e. finding the response to every operation in S and returning the resulting set). We show that the problem of evaluating S is in NC for various combinations of common set-manipulation operations. Once we establish membership in NC (or, if membershp in NC is obvious), we develop...
Vizing [21,22,8] proved that any graph G of maximal degree Δ(G) is either Δ or Δ + 1 colorable. For edge-coloring of planar graphs, he showed that all graphs G with Δ(G) ≥ 8 are Δ-colorable. Based on the proof of Vizing's theorem Gabow et al. [10] designed an O(n2) algorithm for Δ-coloring planar graphs when Δ(G) ≥ 8. Boyar and Karloff [2] proved that this problem belongs to NC if Δ(G)...
Few existing parallel graph algorithms achieve optimality when applied to very sparse graphs such as planar graphs. We add to the list of such algorithms by giving optimal, logarithmic-time PRAM algorithms for the connected components, spanning tree, biconnected components, and strong orientation problems. The algorithms work on classes of graphs including planar graphs and graphs of bounded genus...
We present two new techniques for trimming a logarithmic factor from the running time of efficient parallel algorithms for graph problems. The main application of our techniques is an improvement in running time from O (log2n) to O(logn) for efficient triconnectivity testing in parallel. Additional applications include almost optimal O(logn) time algorithms for recognizing Gauss codes,...
Given two trees, a guest tree G and a host tree H, the subtree isomorphism problem is to determine whether there is a subgraph of H that is isomorphic to G. We present a randomized parallel algorithm for finding such an isomorphism, if it exists. The algorithm runs in time O(log3n) on a CREW PRAM, where n is the number of nodes in H. Randomization is used (solely) to solve each of a series...
All graphs have cycle separators. (A single vertex is regarded as a trivial cycle.) In sequential computation, a cycle separator can be found in O(n + e) time for any undirected graph of n vertices and e edges; in O((n + e) log n) time for any directed graph. In parallel computation, it is in deterministic NC to convert any depth-first search forest of any graph into a cycle separator. Moreover, finding...
Let p be prime and assume that GF(pn) is given via an irreducible nth degree GF(p) polynomial. We exhibit a boolean circuit of size nO(1) and depth O(log(n)) such that for any x ε GF(pn) the circuit produces x−1. The circuit is based upon an interesting connection between finite field computations...
In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs in O(log n) time on EREW P-RAM with n/log n processor. The algorithm matches the performance of the Cole-Vishkin [CV86a] algorithm but is simple and has reasonable constant factors.
Two related results are presented. The first is a simple n/log n processor, O(log n) time parallel algorithm for list ranking. The second is a general parallel algorithmic technique for computations on trees; it yields the first n/log n processor, O(log n) time deterministic parallel algorithm for expression tree evaluation, and solves many other tree problems within the same complexity bounds.
We show that any arithmetic expression of size n can be evaluated on an EREW PRAM with O(n/log n) processors in O (log n) steps. A major contribution is the simplicity of the algorithm. In contrast with existing algorithms which require independent RAKE and COMPRESS operations, our algorithm combines the RAKE and COMPRESS into one simple operation. In fact, our algorithm can be viewed as avoiding...
We consider the following problem. Suppose a rooted tree T is available for preprocessing. Answer on-line queries requesting the lowest common ancestor for any pair of vertices in T. We present a linear time and space preprocessing algorithm which enables us to answer each query in O (1) time, as in Harel and Tarjan [HT-84]. Our algorithm has the advantage of being simple and easily parallelizable...
Automatic parallelization of code written in a sequential language such as FORTRAN is of great importance. One natural approach to loop parallelization is to assign separate invocations of a loop to different processors. However, it is often necessary to delay the starting times of loops to avoid violating data dependences. In this paper we study a scheduling problem, called the Delay Problem, that...
We study the complexity of a generalization of the unit-execution-time multiprocessor scheduling problem under precedence constraints, in which the number of communication arcs is also minimized. Most versions of the problem are shown NP-complete, and two polynomial algorithms are presented for specialized cases.
We show in this paper that a perfect matching of a line graph can be computed in NC. A necessary and sufficient condition for a line graph to have a perfect matching is an even number of vertices. To compute the perfect matching, we use a technique of dividing the graph into kingdoms. This result is equivalent to partitioning the edge set of a graph into edge disjoint paths of even length.
A separation pair of a biconnected graph is a pair of vertices whose removal disconnects the graph. The central part of any algorithm that finds triconnected components is an algorithm for separation pairs. Recently Miller and Ramachandran have given a parallel algorithm that runs in O(log2 n) time using O(m) processors. We present a new algorithm for finding all separation pairs of a biconnected...
The past few years have seen a number of results on graph embeddings that deserve to be called breakthroughs because of their settling hard open problems and/or their raising important issues that promise to alter the direction of subsequent research on graph embeddings. We describe and discuss several such results.
We describe how to embed an arbitrary binary tree with dilation 3 and O(1) expansion into a hypercube. (In fact, we show that all binary trees can be embedded into their optimal hypercube with dilation 3, provided that all binary trees with no more than B vertices, for some fixed number B, can be embedded with dilation 3.) We also show how to embed all binary trees into their optimal hypercube with...
We show that 2-dimensional rectangular grids of large aspect ratio can be embedded into rectangles of smaller aspect ratios with small expansion and dilation. In particular, width can be reduced by a factor of up to 2 with optimal expansion and dilation (2). A factor of 3 can be obtained with dilation 3. In general, any rectangular grid can be embedded into a square grid that is no more than unity...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.